Recent years have seen the rapid advancement and proliferation of electronic devices, which devices often require the updating of the resident firmware, operating code, applications or other software loaded thereon, collectively, “binary images”, or simply “images”. Moreover, installing and updating of such binary images is becoming more routine as advancements applicable to a particular device far outpace the rate at which it is desirable to retire the unit and replace it with an entirely new unit.
Moreover, for many devices for which updating the binary image is desirable, these same devices may be remotely located and it is not practical for many reasons to return or collect the device in order that it can be directly connected to a host updating machine or system.
Additionally, with limited memory on the device itself, whether it is a mobile phone, PDA, pager or any other variety of small form factor portable device, delivery of an entire new image is often infeasible due to the capacity limitations of the device. Also, even if the device is not memory or other resource constrained, and thus not limiting the size or application process for installing an update, delivery of a complete new image may still be infeasible because the connection used by the device may be intermittent and/or of a limited capacity.
Accordingly there is a need for an efficient, effective and reliable system and method for providing an update to a device that does not require the unit to be returned to a service center for update and instead uses an update package that can modify the binary image in-situ, and is significantly smaller than the full image.
A known manner in reducing the size of a new image update is to use a differencing algorithm or Binary Differencing Engine (BDE) to compare the original or existing binary image with the new binary image to produce a list of differences, herein referred to as an ‘update package’. Such differences, in a general sense, are typically output or expressed as sequences or sets of ADD and COPY operations such that the new image can be created by combining together binary sequences copied from the original image resident on the device (a COPY operation) and interlacing them with binary sequences from the new image (contained within the update package) for which a suitable copy sequence was not available in the original image (an ADD operation). The ADD operation specifies a list of bytes that must be copied from the update package into the new image at the current location, and the COPY operation specifies a number of bytes to be copied from a given location in the original image to the current update location in the new image.
ADD or COPY operations identified by the BDE, or candidate operations where more than one is possible at a given location within the image, are supplied to an Update Encoder which is responsible for selecting preferred candidate operations, possibly combining additional available encoding information, and for ultimately producing the final binary update package. This process may involve finding the smallest encoding for each of the required operations together with a final compression phase. One efficient approach to generating update packages is described in U.S. patent application Ser. No. 10/676,483 entitled “Efficient System and Method for Updating a Memory Device”, filed Sep. 30, 2003, the disclosure of which is incorporated herein by reference.
One implication of modifying an original image to create a new image (whether to add new functionality, fix errors or otherwise) is that even small changes to the original image may cause large portions of the image to move in the microprocessor's address space. This effect can cause even logically small changes to create large numbers of alterations in addressing and reference pointers. Thus, though large portions of the original image may only have been moved, the BDE in general may not be able to generate a set of simple COPY operations because of how the embedded transfers of control (e.g. branch or jump instructions) are expressed within the processor's instruction set. The BDE will typically find a very large number of small changes to the image interspersed with short sections of unmodified or purely moved content. Even though the functional change to the image was minor, the resultant detailed changes to the image require the BDE to generate a large number of small modifications (i.e. ADD) to the image interspersed with short sections of purely copied content (i.e. COPY) in order to resolve and reflect the new location for transfers of control. This can result in large update packages even where the functional change to the image was small.
Accordingly, a system or method that can effectively accommodate these changes to control transfers and addressing issues, thereby reducing the size of the resultant update packages would be desirable. More directly, what is needed is an approach to recognize large portions of the original image being moved in the processor's address space. The ability to efficiently express the effect of moving this code/data structure through the address space is key to reducing the update package size.
The need therefore is for a system that reduces the size impact of systematic image changes on the final update package by optimizing the size and number of operations to produce the smallest update package for any given original image and new image. The resulting update package size thus reflects the size of the functional change made to the image rather than its impact at the raw binary level.